class Solution:
    def search(self, nums: list, target: int) -> bool:
        length = len(nums)
        if length < 30:
            return target in nums
        min_i, max_i = 0, length - 1
        i = max_i // 2
        try:
            while (nums[i-1] - nums[i]) * (nums[i+1] - nums[i]) <= 0:
                if nums[i + 1] == nums[i]:
                    nums.pop(i + 1)
                    max_i -= 1
                if nums[i] < nums[0]:
                    max_i = i
                    i = (i+min_i) // 2
                else:
                    min_i = i
                    i = (i+max_i) // 2
                if nums[i - 1] == nums[i]:
                    nums.pop(i)
                    i -= 1
                    max_i -= 1
                # print(i, nums[i], nums)
            if target > nums[0]:
                max_tar, min_tar = i+1, 0
            else:
                max_tar, min_tar = length - 1, i
            j = (max_tar + min_tar) // 2
            while max_tar - min_tar > 1:
                if nums[j] == target:
                    return True
                elif nums[j] < target:
                    min_tar = j
                    j = (j + max_tar) // 2
                else:
                    max_tar = j
                    j = (j + min_tar) // 2
            return False
        except:
            return target in nums



a = Solution()
print(a.search([11, 12, 13, 14, 15, 20, 21, 22, 23, 30, 1, 1, 1, 2, 3, 4, 6, 7, 8, 9, 9, 9, 10], 6))
print(a.search([3,4,4,4,4,4,4,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,10,10,10,-10,-10,
                -10,-9,-8,-8,-8,-8,-8,-7,-7,-7,-7,-6,-6,-6,-6,-6,-6,-6,-5,-5,-5,-4,-4,-4,-4,-3,-3,-3,-3,-3,-3,
                -2,-2,-2,-2,-1,-1,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3], 6))
print(a.search([-9,-9,-9,-8,-8,-7,-7,-7,-7,-6,-6,-6,-6,-6,-6,-6,-6,-6,-5,-5,-5,-5,-5,-4,-4,-4,-3,-3,-3,-3,-3,-3,-2,-2,
       -2,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,-1,0,0,0,1,1,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6
          ,7,7,7,7,7,8,9,9,9,10,10,10,10,10,10,10,-10,-9,-9,-9,-9], 2))
print(a.search([10,10,10,-10,-10,-10,-10,-9,-9,-9,-9,-9,-9,-9,-8,-8,-8,-8,-8,-8,-8,-8,-7,-7,-7,-7,-6,-6,-6,-5,-5,-5,
                -4,-4,-4,-4,-3,-3,-2,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,3,3,3,4,
                4,4,5,5,5,5,6,6,6,7,7,7,7,7,8,8,8,8,9,9,9,9,9,9,9,10,10], -6))
print(a.search([3,3,3,3,4,4,4,4,5,5,5,6,6,6,6,6,6,7,7,8,8,8,8,8,8,8,8,9,9,10,10,10,10,10,-10,-10,-9,-9,-9,-9,-9,-9,-9,
                -9,-9,-8,-8,-8,-8,-8,-8,-7,-7,-7,-6,-6,-6,-6,-6,-6,-6,-6,-6,-6,-5,-5,-5,-5,-5,-5,-4,-4,-4,-4,-4,-3,-3,
                -2,-2,-2,-2,-1,-1,-1,-1,-1,-1,0,0,0,1,1,1,1,1,1,2,2,2,2], 10))